package com.kingwood.algorithm.zuochengyun.dongtaiguihua;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author 22025812
 * @Description: TODO
 * @Date: 2024/3/20 16:58
 * @Modified By：
 * @Version 1.0
 */
public class Code05_MinimumDeleteBecomeSubstring {

    // 暴力方法
    // 为了验证
    public static int minDelete1(String s1, String s2) {
        List<String> list = new ArrayList<>();
        f(s1.toCharArray(), 0, "", list);
        // 排序 : 长度大的子序列先考虑
        // 因为如果长度大的子序列是s2的子串
        // 那么需要删掉的字符数量 = s1的长度 - s1子序列长度
        // 子序列长度越大，需要删掉的字符数量就越少
        // 所以长度大的子序列先考虑
//        list.sort((a, b) -> b.length() - a.length());
//        for (String str : list) {
//            if (s2.indexOf(str) != -1) {
//                // 检查s2中，是否包含当前的s1子序列str
//                return s1.length() - str.length();
//            }
//        }
        return s1.length();
    }

    // 生成s1字符串的所有子序列串
    public static void f(char[] s1, int i, String path, List<String> list) {
        if (i == s1.length) {
            list.add(path);
        } else {
            f(s1, i + 1, path, list);
            f(s1, i + 1, path + s1[i], list);
        }
    }

    public static void main(String[] args) {
        String str = "abc";
        List<String> list = new ArrayList<>();
        f(str.toCharArray(), 0, "", list);
        for (String s : list) {
            System.out.println(s);
        }
    }
}
